class Solution(object):
    def countBits(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        out = [0] * (n + 1)
        for i in range(1, n + 1):
            out[i] = out[i & (i - 1)] + 1
        return out


data = Solution()
n = 5
print(data.countBits(n))